home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / sort / pdsrt321 / pdsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-07  |  13.0 KB  |  490 lines
  1. /*
  2.    ****************************  NOTICE!  **************************
  3.    *   Contrary to the current trend  in  MS-DOS  software  this   *
  4.    *   program,  for  whatever  it is worth,  is NOT copyrighted   *
  5.    *   (with the exception of the runtime library  from  Borland   *
  6.    *   International's  Turbo  C)!  The program,  in whole or in   *
  7.    *   part,  may be used freely in any fashion  or  environment   *
  8.    *   desired.  If  you  find this program to be useful to you,   *
  9.    *   do NOT send any contribution to the author;  in the words   *
  10.    *   of  Rick  Conn,   'Enjoy!'  However,   if  you  make  any   *
  11.    *   improvements,  I would enjoy  receiving  a  copy  of  the   *
  12.    *   modified  source.  I  can  be reached,  usually within 24   *
  13.    *   hours,  by  messages  on  any  of  the  Phoenix  systems,   *
  14.    *   particularly:                                               *
  15.    *                                                               *
  16.    *               Technoids Anonymous     [PCBOARD]               *
  17.    *                   (602) 899-4876   300/1200/2400 bps          *
  18.    *                                                               *
  19.    *   All can be reached through PC Pursuit.                      *
  20.    *                                                               *
  21.    *   or:                                                         *
  22.    *                on GEnie, mail address: DON-WILL               *
  23.    *                on CompuServ:           75410,543              *
  24.    *                                                               *
  25.    *   Every  effort has been made to avoid error and moderately   *
  26.    *   extensive testing has been  performed  on  this  program,   *
  27.    *   however, the author does not warrant it to be fit for any   *
  28.    *   purpose  or  to  be  free  from  error  and disclaims any   *
  29.    *   liability for actual or any other damage arising from the   *
  30.    *   use of this program.                                        *
  31.    *****************************************************************
  32. */
  33.  
  34. #include <stdlib.h>
  35. #include <stdio.h>
  36. #include <string.h>
  37. #include <alloc.h>
  38. #include <ctype.h>
  39. #include <dir.h>
  40. #include <dos.h>
  41. #include <limits.h>
  42.  
  43. #include "queue.h"
  44.  
  45. void            GetArgs(int argc, char *argv[]);
  46. void            InvalArgu(char *Msg);
  47. unsigned        FillSortArray(void);
  48. void            Usage(void);
  49. int             isdevice(int handle);
  50.  
  51. void            Merge(void);
  52. void            GetKeys(void);
  53. void            PutKeys(void);
  54.  
  55. unsigned long   MaxMem;
  56. unsigned        S_ArraySize;
  57. char          **SortArray;
  58. int             KeyCount = 0;
  59. int             RecLen = -1;
  60. unsigned long   DiskAdr = 0;
  61. unsigned long   NextAdr = 0;
  62. unsigned long   EndAdr;
  63. long            TotalRecs = 0;
  64. long            OutCount = 0;
  65. char            *Buffer;
  66. FILE           *fin = NULL;
  67. FILE           *fint, *fout;
  68. unsigned long   lnno = 0;
  69. QUE_DEF        *Keys, Runs;
  70. long            BufSize;
  71. char            IntPath[65] = "";
  72.  
  73. unsigned        DeBug = 0;
  74.  
  75. struct KeyEntry {
  76.     int             Begin;
  77.     int             Len;
  78.     char            Order;
  79.     char            Case;
  80.     char            Type;
  81.     };
  82.  
  83. typedef struct RunStruct {
  84.     unsigned long   Begin;
  85.     unsigned long   Count;
  86.     }               RUN_ENT;
  87.  
  88. char            InputName[65] = "";
  89. char            OutName[65] = "";
  90. char            IntName[65] = "";
  91. long            Temp;
  92. int             QuietSwt = 0;
  93. int                Verbose  = 0;
  94. int                KeySwt     = 0;
  95.  
  96.  void
  97. main (int argc, char *argv[]) {
  98.     extern int      comp();
  99.  
  100.     unsigned        i;
  101.     unsigned        Count;
  102.     RUN_ENT        *r;
  103.     struct dfree    DiskTab;
  104.     char           *p;
  105.     char            OutDisk;
  106.     char            IntDisk;
  107.     long            DiskFree;
  108.     struct KeyEntry *t;
  109.  
  110.     if ((Keys = malloc(sizeof(QUE_DEF))) == NULL) {
  111.         fprintf(stderr, "Insufficient memory for Key queue.\n");
  112.         exit(12);
  113.         }
  114.     InitQueue(Keys);
  115.     InitQueue(&Runs);
  116.     if (argc < 2) {
  117.         fin = stdin;
  118.         fout = stdout;
  119.         }
  120.     else {
  121.         GetArgs(argc, argv);
  122.         }
  123.     if (RecLen == -1) RecLen = 258;
  124.     if (!QuietSwt)
  125.         fprintf(stderr, "PDSORT Version 3.2.1:  September 7, 1991\n");
  126.     if ( (Buffer = malloc(RecLen + 2)) == NULL) {
  127.         fprintf(stderr, "Insufficient memory for input buffer!\n");
  128.         exit(1);
  129.         }
  130.     if (fin != stdin) {
  131.         if ( (KeySwt) && !strcmp(InputName, OutName) ) {
  132.             fprintf(stderr, "With the key sort option (-k),"
  133.                     " the input and output files must be different.\n");
  134.             exit(20);
  135.             }
  136.         if ((fin = fopen(InputName, "r")) == NULL) {
  137.             fprintf(stderr, "I can't find input file: %s", InputName);
  138.             perror("");
  139.             exit(2);
  140.             }
  141.         }
  142.     if (!isdevice(fileno(fin))) {
  143.         fseek(fin, 0, SEEK_END);
  144.         EndAdr = ftell(fin);
  145.         fseek(fin, 0, SEEK_SET);
  146.         }
  147.     else EndAdr = 0;
  148.  
  149.     if (fin != stdin) {
  150.         if ((p = strchr(OutName, ':')) != NULL) OutDisk = toupper(OutName[0]) - '@';
  151.         else OutDisk = getdisk() + 1;
  152.         getdfree(OutDisk, &DiskTab);
  153.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  154.         if (DiskTab.df_sclus == 0xFFFFU) {
  155.             perror("Bad getdfree()");
  156.             exit(15);
  157.             }
  158.         if (DiskFree < EndAdr) {
  159.             fprintf(stderr, "Insufficient space on output disk.\n");
  160.             exit(5);
  161.             }
  162.         if (IntPath[0] != '\0') {
  163.             if (IntPath[1] == ':') IntDisk = toupper(IntPath[0]) - '@';
  164.             else IntDisk = getdisk() + 1;
  165.             }
  166.         else {
  167.             if ((p = strrchr(OutName, '\\')) != NULL)
  168.                 strncpy(IntPath, OutName, (int) (p - OutName + 1));
  169.             else {
  170.                 IntPath[0] = OutDisk + '@';
  171.                 IntPath[1] = ':';
  172.                 IntPath[2] = '\\';
  173.                 getcurdir(OutDisk, &IntPath[3]);
  174.                 }
  175.             if (strchr(IntPath, ':') == NULL) IntDisk = OutDisk;
  176.             else IntDisk = IntPath[0] - '@';
  177.             }
  178.         getdfree(IntDisk, &DiskTab);
  179.         DiskFree = (long) DiskTab.df_avail * DiskTab.df_sclus * DiskTab.df_bsec;
  180.         if (DiskFree < EndAdr) {
  181.             fprintf(stderr, "Insufficient space on intermediate disk.\n");
  182.             exit(6);
  183.             }
  184.         }
  185.     if (Keys->Count == 0) {
  186.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  187.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  188.             exit(12);
  189.             }
  190.         t->Order = 'a';
  191.         t->Case = 'm';
  192.         t->Type = 'c';
  193.         t->Begin = 0;
  194.         t->Len = RecLen;
  195.         Enque(Keys, t);
  196.         }
  197.  
  198.     if (KeySwt) GetKeys();
  199.  
  200.     MaxMem = coreleft();
  201.     MaxMem -= 4 * 1024L;
  202.  
  203.     S_ArraySize = (unsigned) (MaxMem / (RecLen + 2 + sizeof(char far *) + 10));
  204.     if (S_ArraySize > UINT_MAX / sizeof(char far *))
  205.         S_ArraySize = UINT_MAX / sizeof(char far *);
  206.     if ((SortArray = malloc(S_ArraySize * sizeof(char far *))) == NULL) {
  207.         fprintf(stderr, "Major Error! Insufficient memory for Sort Array.\n");
  208.         exit(12);
  209.         }
  210.  
  211.     for (i = 0;
  212.          (i < S_ArraySize && coreleft() >= ((4 * 1024L) + RecLen + 2));
  213.          i++) {
  214.         if ((SortArray[i] = malloc(RecLen + 2)) == NULL) {
  215.             fprintf(stderr, "Major Error! Insufficient memory for sort item.\n");
  216.             exit(12);
  217.             }
  218.         }
  219.     S_ArraySize = i;
  220.     if (!QuietSwt)
  221.         fprintf(stderr, "Max records per run = %d\n", S_ArraySize);
  222.  
  223.     BufSize = (coreleft() - 1024) / 2;
  224.  
  225.     if (Verbose && !QuietSwt) printf(" Run # %d\n", Runs.Count + 1);
  226.     Count = FillSortArray();
  227.  
  228.     TotalRecs += Count;
  229.     if (NextAdr >= EndAdr) {
  230.         if (!QuietSwt)
  231.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  232.         if (fin != stdin) {
  233.             fclose(fin);
  234.             if ((fout = fopen(OutName, "w")) == NULL) {
  235.                 fprintf(stderr, "I can't create output file: %s", OutName);
  236.                 perror("");
  237.                 exit(7);
  238.                 }
  239.             }
  240.         errno = 0;
  241.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  242.         qsort(SortArray, Count, sizeof(char far *), comp);
  243.  
  244.         if (Verbose && !QuietSwt) printf("\tWriting\n");
  245.         for (i = 0; i < Count; i++) {
  246.             fputs(SortArray[i], fout);
  247.             if (errno) {
  248.                 perror("I/O error on output file");
  249.                 exit(8);
  250.                 }
  251.             OutCount++;
  252.             }
  253.         if (fout != stdout) fclose(fout);
  254.         for (i=0; i < S_ArraySize; ++i) free(SortArray[i]);
  255.         free(SortArray);
  256.         if (KeySwt)
  257.             PutKeys();
  258.         }
  259.     else {
  260.         while (Count > 0) {
  261.             if (fint == NULL) {
  262.                 strcpy(IntName, IntPath);
  263.                 strcat(IntName, "\\SORT.$$$");
  264.                 if ((fint = fopen(IntName, "w")) == NULL) {
  265.                     fprintf(stderr, "I can't create sort intermediate file: %s", IntName);
  266.                     perror("");
  267.                     exit(9);
  268.                     }
  269.                 errno = 0;
  270.                 }
  271.             DiskAdr = ftell(fint);
  272.  
  273.             if (Verbose && !QuietSwt) printf("\tSorting\n");
  274.             qsort(SortArray, Count, sizeof(char far *), comp);
  275.  
  276.             if ((r = malloc(sizeof(RUN_ENT))) == NULL) {
  277.                 fprintf(stderr, "Insufficient memory for Run Entry!\n");
  278.                 exit(12);
  279.                 }
  280.             r->Begin = DiskAdr;
  281.             r->Count = Count;
  282.             Enque(&Runs, r);
  283.  
  284.             if (Verbose && !QuietSwt) printf("\tWriting\n");
  285.             for (i = 0; i < Count; i++) {
  286.                 fputs(SortArray[i], fint);
  287.                 if (errno) {
  288.                     perror("I/O error on intermediate file");
  289.                     exit(10);
  290.                     }
  291.                 }
  292.             if (Verbose && !QuietSwt) printf("    Run # %d\n", Runs.Count + 1);
  293.             Count = FillSortArray();
  294.             TotalRecs += Count;
  295.             }
  296.         if (!QuietSwt)
  297.             fprintf(stderr, "Total records read = %ld\n", TotalRecs);
  298.         if (fin != stdin) {
  299.             fclose(fin);
  300.             if ((fout = fopen(OutName, "w")) == NULL) {
  301.                 fprintf(stderr, "I can't create output file: %s", OutName);
  302.                 perror("");
  303.                 exit(7);
  304.                 }
  305.             }
  306.         errno = 0;
  307.         if (Verbose && !QuietSwt) printf("\tSorting\n");
  308.         qsort(SortArray, Count, sizeof(char far *), comp);
  309.         for (i = 0; i < Count; i++) {
  310.             fputs(SortArray[i], fout);
  311.             if (errno) {
  312.                 perror("I/O error on output file");
  313.                 exit(8);
  314.                 }
  315.             }
  316.         Merge();
  317.         }
  318.     unlink(IntName);
  319.     if (!QuietSwt)
  320.         fprintf(stderr, "Total records written = %ld\n", OutCount);
  321.     exit(0);
  322.     }
  323.  
  324.  
  325.  void
  326. GetArgs (int argc, char *argv[]) {
  327.     extern int      QuietSwt;
  328.     extern int        Verbose;
  329.  
  330.     int             i;
  331.     char           *p1, *p2;
  332.     struct KeyEntry *t;
  333.  
  334.     for (i = 1; i < argc; ++i) {
  335.         if (argv[i][0] != '-') continue;
  336.         if (!strcmp(argv[i], "-")) {
  337.             fin = stdin;
  338.             fout = stdout;
  339.             continue;
  340.             }
  341.         switch (tolower(argv[i][1])) {
  342.             case 't':
  343.                 strcpy(IntPath, &argv[i][2]);
  344.                 break;
  345.             case 'q':
  346.                 QuietSwt = 1;
  347.                 break;
  348.             case 'v':
  349.                 Verbose = 1;
  350.                 break;
  351.             case 'k':
  352.                 KeySwt = 1;
  353.                 break;
  354.             default:
  355.                 fprintf(stderr, "Invalid option: %s\n", argv[i]);
  356.                 Usage();
  357.             }
  358.         }
  359.  
  360.     for (i = 1; i < argc; ++i) {
  361.         if (argv[i][0] == '-') continue;
  362.         if (fin == NULL) {
  363.             if (InputName[0] == '\0') {
  364.                 strcpy(InputName, argv[i]);
  365.                 continue;
  366.                 }
  367.             else if (OutName[0] == '\0') {
  368.                 strcpy(OutName, argv[i]);
  369.                 continue;
  370.                 }
  371.             }
  372.         p1 = argv[i];
  373.         if (!isdigit(p1[0])) InvalArgu(argv[i]);
  374.         if ((RecLen == -1) && (strspn(p1, "0123456789") == strlen(p1))) {
  375.             RecLen = atoi(argv[i]);
  376.             continue;
  377.             }
  378.         p2 = &p1[strspn(p1, "0123456789")];
  379.         if ((t = malloc(sizeof(struct KeyEntry))) == NULL) {
  380.             fprintf(stderr, "Insufficient memory for Key entry.\n");
  381.             exit(12);
  382.             }
  383.         t->Order = 'a';
  384.         t->Case = 'm';
  385.         t->Type = 'c';
  386.         t->Begin = atoi(p1) - 1;
  387.         if (*p2 == ':') t->Len = atoi(++p2);
  388.         else if (*p2 == '-') t->Len = atoi(++p2) - t->Begin;
  389.         else InvalArgu(argv[i]);
  390.         p1 = p2;
  391.         p2 = &p1[strspn(p1, "0123456789")];
  392.         if (*p2 == ':') {
  393.             p1 = ++p2;
  394.             while (*p1 != '\0') {
  395.                 switch (tolower(*p1++)) {
  396.                     case 'd':
  397.                         t->Order = 'd';
  398.                         break;
  399.                     case 'a':
  400.                         t->Order = 'a';
  401.                         break;
  402.                     case 'i':
  403.                         t->Case = 'i';
  404.                         break;
  405.                     case 'm':
  406.                         t->Case = 'm';
  407.                         break;
  408.                     case 'c':
  409.                         t->Type = 'c';
  410.                         break;
  411.                     default:
  412.                         InvalArgu(argv[i]);
  413.                     }
  414.                 }
  415.             }
  416.         else if (*p2 != '\0') InvalArgu(argv[i]);
  417.         Enque(Keys, t);
  418.         }
  419.     }
  420.  
  421.  void
  422. InvalArgu (char *Msg) {
  423.     fprintf(stderr, "Invalid argument: %s.\n", Msg);
  424.     Usage();
  425.     }
  426.  
  427.  
  428.  unsigned
  429. FillSortArray (void) {
  430.     int             i;
  431.  
  432.     if (Verbose && !QuietSwt) printf("\tReading\n");
  433.     for (i = 0; i < S_ArraySize; i++) {
  434.         errno = 0;
  435.         if (fgets(Buffer, RecLen + 2, fin) == NULL) return (i);
  436.         if (errno) {
  437.             perror("I/O error on input file");
  438.             exit(3);
  439.             }
  440.         NextAdr = ftell(fin);
  441.         lnno++;
  442.         if (Buffer[strlen(Buffer) - 1] != '\n') {
  443.             fprintf(stderr, "Record #%lu exceeds maximum length %d\n",
  444.                     lnno, RecLen);
  445.             exit(4);
  446.             }
  447.         strcpy(SortArray[i], Buffer);
  448.         }
  449.     return (i);
  450.     }
  451.  
  452.  
  453.  int
  454. comp (const void *aa, const void *bb) {
  455.     char          **a, **b;
  456.     char            HoldA, HoldB;
  457.     int             End, Result;
  458.     QUE_ENTRY      *t;
  459.     struct KeyEntry *v;
  460.  
  461.     a = (char **) aa;
  462.     b = (char **) bb;
  463.     if (*a == *b) return (0);
  464.     if (*a == NULL) return (1);
  465.     if (*b == NULL) return (-1);
  466.     for (Result = 0, t = Keys->Head; (t != NULL) && (Result == 0); t = t->Next) {
  467.         v = t->Body;
  468.         End = v->Begin + v->Len;
  469.         HoldA = (*a)[End];
  470.         (*a)[End] = '\0';
  471.         HoldB = (*b)[End];
  472.         (*b)[End] = '\0';
  473.         Result = (v->Order == 'a') ?
  474.             (v->Case == 'i') ? stricmp(&(*a)[v->Begin], &(*b)[v->Begin])
  475.             : strcmp(&(*a)[v->Begin], &(*b)[v->Begin])
  476.             : (v->Case == 'i') ? stricmp(&(*b)[v->Begin], &(*a)[v->Begin])
  477.             : strcmp(&(*b)[v->Begin], &(*a)[v->Begin]);
  478.         (*a)[End] = HoldA;
  479.         (*b)[End] = HoldB;
  480.         }
  481.     return (Result);
  482.     }
  483.  
  484.  
  485.  void
  486. Usage (void) {
  487.     fprintf(stderr, "USAGE: pdsort input_file output_file rec_len\n");
  488.     exit(1);
  489.     }
  490.